package week_10;

public class NumArraySegmentTree {

    public class SegmentTree {
        int n;
        Node[] a;

        public class Node {
            int l, r;
            int sum;
            int mark;
        }

        public SegmentTree(int[] nums) {
            n = nums.length;
            a = new Node[4 * n];
            build(1, 0, n - 1, nums);
        }

        public void Change(int index, int val) {
            change(1, index, val);
        }


        public int Query(int l, int r) {
            return query(1, l, r);
        }


        private void build(int curr, int l, int r, int[] nums) {
            a[curr] = new Node();
            a[curr].l = l;
            a[curr].r = r;
            a[curr].mark = 0;
            if (l == r) {
                a[curr].sum = nums[l];
                return;
            }
            int mid = (l + r) >> 1;
            // 建左树
            build(curr * 2, l, mid, nums);
            // 建右树
            build(curr * 2 + 1, mid + 1, r, nums);
            // 回溯时自底向上回溯信息
            a[curr].sum = a[curr * 2].sum + a[curr * 2 + 1].sum;
        }

        // 单点修改：先递归找到，然后自底向上统计信息
        private void change(int curr, int index, int val) {
            // 递归边界：叶子[index, index]
            if (a[curr].l == a[curr].r) {
                a[curr].sum = val;
                return;
            }
            spread(curr);
            int mid = (a[curr].l + a[curr].r) >> 1;
            if (index <= mid) change(curr * 2, index, val);
            else change(curr * 2 + 1, index, val);
            a[curr].sum = a[curr * 2].sum + a[curr * 2 + 1].sum;
        }

        // 递归求区间和
        // 完全包含：直接返回
        // 否则：左右划分 -- 找到左右里 子完全包含的节点返回累加
        private int query(int curr, int l, int r) {
            // 被范围完全覆盖的直接返回sum值
            // 如果超出一部分就需要往下继续深入迭代
            if (l <= a[curr].l && r >= a[curr].r) return a[curr].sum;
            spread(curr);
            int mid = (a[curr].l + a[curr].r) >> 1;
            int ans = 0;
            if (l <= mid) ans += query(curr * 2, l, r);
            if (r > mid) ans += query(curr * 2 + 1, l, r);
            return ans;
        }

        // 区间修改
        public void change(int curr, int l, int r, int delta) {
            // 区间被完全包含
            if (l <= a[curr].l && r >= a[curr].r) {
                a[curr].sum += delta * (a[curr].r - a[curr].l + 1);
                a[curr].mark = delta;
            }
            spread(curr);
            int mid = (a[curr].l + a[curr].r) >> 1;
            if (l <= mid) change(curr * 2, l, r, delta);
            if (r > mid) change(curr * 2 + 1, l, r, delta);
            a[curr].sum = a[curr * 2].sum + a[curr * 2 + 1].sum;
        }

        private void spread(int curr) {
            // 有bug标记 只修改到子树
            if (a[curr].mark != 0) {
                a[curr * 2].sum += a[curr].mark * (a[curr * 2].r - a[curr * 2].l + 1);
                a[curr * 2].mark = a[curr].mark;
                a[curr * 2 + 1].sum = a[curr].mark * (a[curr * 2 + 1].r - a[curr * 2 + 1].l + 1);
                a[curr * 2 + 1].mark = a[curr].mark;
                a[curr].mark = 0;
            }
        }

    }

    SegmentTree segmentTree;

    public NumArraySegmentTree(int[] nums) {
        segmentTree = new SegmentTree(nums);
    }

    public void update(int index, int val) {
        segmentTree.Change(index, val);


    }

    public int sumRange(int left, int right) {
        return segmentTree.Query(left, right);
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5};
        NumArraySegmentTree numArray = new NumArraySegmentTree(nums);
        int ans = numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
        System.out.println(ans);
        numArray.update(1, 2);   // nums = [1,2,5]
        ans = numArray.sumRange(0, 2);
        System.out.println(ans);
    }
}
